package main.leetcode.clockin.May;

import java.util.Arrays;

/**
 * 1371.每个元音包含偶数次的最长字符串
 *
 * <p>给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 'a'，'e'，'i'，'o'，'u' ，在子字符串中都恰好出现了偶数次。
 *
 * <p>
 *
 * <p>示例 1：输入：s = "eleetminicoworoep" 输出：13 解释：最长子字符串是 "leetminicowor" ，它包含 e，i，o 各 2 个，以及 0 个 a，u 。
 *
 * <p>示例 2：>输入：s = "leetcodeisgreat" 输出：5 解释：最长子字符串是 "leetc" ，其中包含 2 个 e 。
 *
 * <p>示例 3：输入：s = "bcbcbc" 输出：6 解释：这个示例中，字符串 "bcbcbc" 本身就是最长的，因为所有的元音 a，e，i，o，u 都出现了 0 次。
 *
 * <p>提示：1 <= s.length <= 5 x 10^5 s 只包含小写英文字母。
 *
 * <p>来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-the-longest-substring-containing-vowels-in-even-counts
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day20 {
    public static void main(String[] args) {
        System.out.println(new day20().findTheLongestSubstring("eleetminicoworoep"));
        System.out.println(new day20().findTheLongestSubstring("leetcodeisgreat"));
    }

    /** 哈希记录状态 */
    public int findTheLongestSubstring(String s) {
        int res = 0;
        // 记录每种状态对应位置位置
        int[] pos = new int[1 << 5];
        Arrays.fill(pos, -1);
        // 初始化0的情况，一个字符都未读入时是肯定满足要求的
        pos[0] = 0;
        int[] cnt = new int[5];
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            switch (c) {
                case 'a':
                    ++cnt[0];
                    break;
                case 'e':
                    ++cnt[1];
                    break;
                case 'i':
                    ++cnt[2];
                    break;
                case 'o':
                    ++cnt[3];
                    break;
                case 'u':
                    ++cnt[4];
                    break;
                default:
                    break;
            }
            int status = 0;
            for (int j = 0; j < 5; j++) {
                // a %= 2; b %= 2; c %= 2; d %= 2; e %= 2; f %= 2;
                // status = 32 * a + 16 * b + 8 * c + 4 * d + 2 * e + f;
                status += (cnt[j] % 2) * (1 << j);
            }
            if (pos[status] >= 0) {
                res = Math.max(res, i + 1 - pos[status]);
            } else {
                // 更新
                pos[status] = i + 1;
            }
        }
        return res;
    }

    //    /** 二进制记录状态 */
    //    public int findTheLongestSubstring(String s) {
    //        /*
    //         利用二进制串来标识 a e i o u 五个字母出现的奇偶性，0表示出现偶数次，1表示出现奇数次
    //         利用pos数组来记录各status首次出现时的下标i，表示s中0-i的子串的字符分布呈status
    //         只要status再次出现，就说明两次之间是一个符合要求的子串
    //         因为中间只要出现过奇数次目标字符，通过亦或就会改变status，而偶数次出现则不会改变status
    //        */
    //        int status = 0;
    //        int res = 0;
    //        // 记录每种状态对应位置位置
    //        int[] pos = new int[1 << 5];
    //        Arrays.fill(pos, -1);
    //        // 初始化0的情况，一个字符都未读入时是肯定满足要求的
    //        pos[0] = 0;
    //        for (int i = 0; i < s.length(); ++i) {
    //            char c = s.charAt(i);
    //            switch (c) {
    //                case 'a':
    //                    status ^= 1;
    //                    break;
    //                case 'e':
    //                    status ^= 1 << 1;
    //                    break;
    //                case 'i':
    //                    status ^= 1 << 2;
    //                    break;
    //                case 'o':
    //                    status ^= 1 << 3;
    //                    break;
    //                case 'u':
    //                    status ^= 1 << 4;
    //                    break;
    //                default:
    //                    break;
    //            }
    //            if (pos[status] >= 0) {
    //                res = Math.max(res, i + 1 - pos[status]);
    //            } else {
    //                // 更新
    //                pos[status] = i + 1;
    //            }
    //        }
    //        return res;
    //    }
}
